Computer security, and in particular file security, can be enforced through the use of access control techniques. In a typical computer system, the operating system typically enforces access control by allowing users to set various access lists that determine which users can and cannot access particular files. When a particular user attempts to access a particular file, if they are not authorized to access the file, the operating system will generally not allow them to do so. One problem with an operating system-enforced security method is that it assumes that the operating system has not been compromised. Specifically, if an operating system becomes compromised, it is quite natural to assume that any security measures administered by the operating system have a high degree of likelihood of becoming compromised as well. Thus, access control techniques are to a large extent only as good as the integrity of the operating system that enforces them.
Compounding this problem to a large degree is the tremendous growth in the popularity of personal computers, e.g. lap top computers. Specifically, many times, individuals will store confidential files on their personal or lap top computers. But, because these computers, by their very nature, are quite mobile, the chances that they will be stolen increases. For example, it is less likely that a computer will be stolen from a secure residence, than from a somewhat unsecure hotel room.
Encryption has evolved as a way to protect files in a way that is independent of the integrity of the operating system of the computer. Encryption typically involves encrypting a file with an encryption key before it is stored on the computer's hard disk. The encryption key is not stored on the computer. Anyone who is authorized to view the file can be provided with the appropriate encryption key. Those individuals who are not authorized to view an encrypted file are not provided with the appropriate encryption key. The file cannot be decrypted without the appropriate encryption (or decryption) key. Thus, if a computer (or its operating system) is compromised, the encrypted file is utterly worthless to anyone who does not have the appropriate key to decrypt the file.
While encryption works well at protecting files in computer systems, there are aspects of computer systems to which encryption poses significant challenges. One particular aspect is a so-called single instance store (SIS) system. Specifically, the contents of a file of a file system may be identical to the contents stored in one or more other files. While some file duplication tends to occur on an individual user's personal computer, duplication is particularly prevalent on networks that are set up with a server that centrally stores the contents of multiple personal computers. For example, with a remote boot facility on a computer network, each user boots from that user's private directory on a file server. Each private directory thus ordinarily includes a number of files that are identical to files on other users' directories. Storing the private directories on traditional file systems consumes a great deal of disk and server file buffer cache space. To address the problems associated with storing multiple identical files on a computer, Microsoft developed the single instance store (SIS) system that is packaged as part of the Windows 2000 operating system. The SIS system reduces file duplication by automatically identifying common identical files of a file system, and then merging the files into a single instance of the data having one or more logically separate links thereto that represent the original files. In this way, the storage impact that multiple duplicate files have on a computer system is reduced.
Encryption complicates the SIS methodology in the following way. Assume that each of a number of individuals encrypts an identical file using their own unique key. The encryption of each file yields ciphertext that is itself different from the ciphertext of each of the other encrypted files. When this happens, there is no realistic way to combine the identical files because the ciphertext for each is different. That is, all that the SIS system will see is the different ciphertext for each file. Accordingly, the SIS system will treat the different ciphertexts for each file as constituting a different file when, in actuality, the files that resulted in the ciphertext are identical.
Accordingly, this invention arose out of concerns associated with improving cryptographic protocols. This invention also arose out of concerns associated with improving the efficiency of single instance store file systems in view of the movement toward using cryptography as a means of file protection.